//hdu2544
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int inf = 1<<25;
int n, m;

struct node
{
	int to;
	int cost;
};

void add_edge(vector<vector<node> > & graph, int x, int y, int c)
{
	graph[x].push_back({y, c});
}

int dijkstra(vector<vector<node> > & graph, int source, int target)
{
	int v = graph.size();
	int dist[v];
//	bool visited[v];
//	fill(visited, visited+v, false);
	fill(dist, dist+v, inf);
	dist[source] = 0;
	typedef pair<int, int> end_cost;
	struct cmp
	{
		bool operator()(const end_cost & a, const end_cost & b) { return a.second > b.second; }
	};
	priority_queue<end_cost, vector<end_cost>, cmp> pq;
	pq.push(make_pair(source, 0));
	while (!pq.empty()) {
		end_cost tmp = pq.top();
		pq.pop();
		int u = tmp.first;
		if (dist[u] < tmp.second) continue;
	//	if (visited[u]) continue;
	//	visited[u] = true;
		for (vector<node>::iterator edge = graph[u].begin();
		 		edge != graph[u].end(); edge++) {
			if (dist[(*edge).to] > dist[u] + (*edge).cost) {
				dist[(*edge).to] = dist[u] + (*edge).cost;
				pq.push(make_pair((*edge).to, dist[(*edge).to]));
			}
		}
	}
	return dist[target];
}

int main()
{
	ios::sync_with_stdio(false);
	while (cin >> n >> m && (n != 0 && m != 0)) {
		vector<vector<node> > graph;
		graph.resize(n);
		for (int i = 0; i < m; i++) {
			int x, y, cost;
			cin >> x >> y >> cost;
			x--; y--;
			add_edge(graph, x, y, cost);
			add_edge(graph, y, x, cost);
		}
		cout << dijkstra(graph, 0, n-1) << endl;
	}
}
